import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-05-10
 * Time:16:40
 */

/**
 * Jz34 二叉树中和为某一值的路径(二)
 */

public class FindPath {
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<Integer>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        dsf(root,expectNumber);
        return lists;
    }

    public void dsf(TreeNode root, int expectNumber) {
        if (root == null) {
            return;
        }
        path.add(root.val);

        expectNumber = expectNumber - root.val;
        if (root.left == null && root.right == null && expectNumber == 0) {
            lists.add(new ArrayList<Integer>(path));
        }
        dsf(root.left, expectNumber);
        dsf(root.right, expectNumber);
        path.pollLast();
    }
}
